﻿/*
题目: 买卖股票的最佳时机 VI

给你一个整数数组 prices 和一个整数 k ，其中 prices[i] 是某支给定的股票在第 i 天的价格。

设计一个算法来计算你所能获取的最大利润。你最多可以完成 k 笔交易。也就是说，你最多可以买 k 次，卖 k 次。

注意：你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。
 
https://leetcode.cn/problems/best-time-to-buy-and-sell-stock-iv/description/
*/

#include <iostream>
#include <random>
#include <string>
#include <vector>
#include <list>
#include "TreeNode.hpp"
#include "ListNode.hpp"
#include <map>
#include <set>
#include <stack>
#include <queue>
#include <unordered_map>
#include <unordered_set>
#include <algorithm>
#include <functional>

using namespace std;

class Solution {
public:
    // 比如第一次购买的情况，分为两种，分别是持有和购买
#define SELL(i) (2 * (i))
#define HAS(i)  (2 * (i) + 1)

// i 表示第 (i + 1) 次购买和持有的情况
    int maxProfit(int k, vector<int>& prices) {
        vector<vector<int>> dp(k * 2, vector<int>(prices.size(), INT_MIN));
        dp[HAS(0)][0] = -prices[0];

        int res = 0;
        for (int i = 1; i < prices.size(); i++) {
            // 先更新第一次购买
            dp[HAS(0)][i] = max(dp[HAS(0)][i - 1], -prices[i]);
            dp[SELL(0)][i] = max(dp[SELL(0)][i - 1], dp[HAS(0)][i - 1] + prices[i]);
            res = max(res, dp[SELL(0)][i]);

            // 只有进行了上一次操作之后，才可以进行后续的操作
            for (int t = 1; t < k; t++) {
                if (dp[SELL(t - 1)][i - 1] > 0) {
                    dp[HAS(t)][i] = max(dp[HAS(t)][i - 1], dp[SELL(t - 1)][i - 1] - prices[i]);
                    dp[SELL(t)][i] = max(dp[SELL(t)][i - 1], dp[HAS(t)][i - 1] + prices[i]);
                    res = max(res, dp[SELL(t)][i]);
                }
                else {
                    break;
                }
            }
        }

        return res;
    }
};